package graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import javafx.util.Pair;

/**
 * 构造函数
 *
 * 编辑：
 *  序号为u和v的两个点之间插入边
 *  删除边
 *
 * 方法：
 *  获取图的顶点数
 *  获取边的条数
 *  获取图的类型
 *  获取某个顶点的边
 *  获取入度、出度、度
 *  判断一个图是否为一棵树
 *  判断有向图是否有环
 *
 * 遍历：
 *  深度优先遍历图
 *  广度优先遍历图
 */
class GraphTest {

    public static final int UNDIRECTED = 0;
    public static final int DIRECTED = 1;

    private int type;
    private int[][] adjacentMatrix;

    public static void main(String[] args) {
        int[][] adjacentMatrix = new int[][]{
                {0, 1, 1, 0, 0, 0},
                {1, 0, 0, 0, 1, 1},
                {1, 0, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0},
                {0, 1, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 0}};
//        GraphTest object = new GraphTest(adjacentMatrix, UNDIRECTED);
//        System.out.println("indegree: " + object.getInDegree(0));
//        System.out.println("outdegree: " + object.getOutDegree(0));
//        object.dfs();
//        object.bfs();

        GraphTest test2 = new GraphTest(5, DIRECTED);
        test2.addEdge(0, 1);
        test2.addEdge(1, 4);
        test2.addEdge(0, 2);
        test2.addEdge(2, 1);
        test2.addEdge(4, 3);
        test2.addEdge(4, 2);
        System.out.println(test2.hasCircle(1, 1, true));
    }

    GraphTest(int[][] adjacentMatrix, int type ) {
        this.adjacentMatrix = adjacentMatrix;
        this.type = type;
    }

    // 初始化邻接矩阵
    GraphTest(int n, int type) {
        this.type = type;
        adjacentMatrix = new int[n][n];
    }

    // 添加边
    void addEdge(int u, int v) {
        if (u < 0 || u >= adjacentMatrix.length || v < 0 || v >= adjacentMatrix.length) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        if (type == UNDIRECTED) {
            adjacentMatrix[u][v] = 1;
            adjacentMatrix[v][u] = 1;
        } else {
            adjacentMatrix[u][v] = 1;
        }
    }

    // 有权图添加边
    void addEdge(int u, int v, int weight) {
        if (u < 0 || u >= adjacentMatrix.length || v < 0 || v >= adjacentMatrix.length) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        adjacentMatrix[u][v] = weight;
    }

    // 删除边
    void deleteEdge(int u, int v) {
        if (u < 0 || u >= adjacentMatrix.length || v < 0 || v >= adjacentMatrix.length) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        if (type == UNDIRECTED) {
            adjacentMatrix[u][v] = 0;
            adjacentMatrix[v][u] = 0;
        } else {
            adjacentMatrix[u][v] = 0;
        }
    }

    // 获取图的顶点数
    int getVertexCount() {
        return adjacentMatrix.length;
    }

    // 获取边的条数
    int getEdgeCount() {
        int res = 0;
        if (type == UNDIRECTED) {
            for (int i = 0; i < adjacentMatrix.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (adjacentMatrix[i][j] != 0) {
                        res++;
                    }
                }
            }
        } else {
            for (int i = 0; i < adjacentMatrix.length; i++) {
                for (int j = 0; j < adjacentMatrix.length; j++) {
                    if (adjacentMatrix[i][j] != 0) {
                        res++;
                    }
                }
            }
        }
        return res;
    }

    int getGraphType() {
        return type;
    }

    List<Pair<Integer, Integer>> getEdgeOfVertex(int u) {
        if (u < 0 || u >= adjacentMatrix.length) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        List<Pair<Integer, Integer>> res = new ArrayList<>();
        for (int i = 0; i < adjacentMatrix.length; i++) {
            if (adjacentMatrix[i][u] != 0) {
                res.add(new Pair<>(i, u));
            }
        }
        for (int j = 0; j < adjacentMatrix.length; j++) {
            if (adjacentMatrix[u][j] != 0) {
                res.add(new Pair<>(u, j));
            }
        }
        return res;
    }

    int getInDegree(int u) {
        if (u < 0 || u >= adjacentMatrix.length) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        int res = 0;
        for (int i = 0; i < adjacentMatrix.length; i++) {
            if (adjacentMatrix[i][u] != 0) {
                res++;
            }
        }
        return res;
    }

    int getOutDegree(int u) {
        if (u < 0 || u >= adjacentMatrix.length) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        int res = 0;
        for (int j = 0; j < adjacentMatrix.length; j++) {
            if (adjacentMatrix[u][j] != 0) {
                res++;
            }
        }
        return res;
    }

    int getDegree(int u) {
        return getInDegree(u) + getOutDegree(u);
    }

    /**
     * 这个方法是错的，无向图的入度大于2并不能说明说明
     * @
     */
    @Deprecated
    boolean isTreeWrong() {
        boolean hasFindRoot = false;
        for (int i = 0; i < adjacentMatrix.length; i++) {
            int inDegree = getInDegree(i);
            if (inDegree > 1) {
                return false;
            }
            if (!hasFindRoot && inDegree == 0 && getOutDegree(i) > 0) {
                hasFindRoot = true;
            } else if (inDegree != 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 树的条件
     * 1：所有结点都是联通的
     * 2：n个结点只有n-1条边(保证1对n)
     *
     * 联通用并查集来判断
     */
    boolean isTree() {
        return false;
    }

    void bfs() {
        boolean[] visited = new boolean[adjacentMatrix.length];
        LinkedList<Integer> level = new LinkedList<>();
        level.offer(0);
        visited[0] = true;
        while (!level.isEmpty()) {
            int cur = level.poll();
            System.out.println("cur: " + cur);
            for (int j = 0; j < adjacentMatrix.length; j++) {
                if (adjacentMatrix[cur][j] != 0) {
                    if (!visited[j]) {
                        level.add(j);
                        visited[j] = true;
                    }
                }
            }
        }
    }

    void dfs() {
        boolean[] visited = new boolean[adjacentMatrix.length];
        visited[0] = true;
        dfs(0, visited);
    }

    private void dfs(int u, boolean[] visited) {
        System.out.println("cur " + u);
        for (int j = 0; j < adjacentMatrix.length; j++) {
            if (visited[j]) {
                continue;
            }
            if (adjacentMatrix[u][j] != 0) {
                visited[j] = true;
                dfs(j, visited);
            }
        }
    }

    // 判断有向图是否有环
    private boolean hasCircle(int u, int cur, boolean isFirst) {
        if (!isFirst && cur == u) {
            return true;
        }
        System.out.println("u " + u + " cur " + cur);
        for (int j = 0; j < adjacentMatrix.length; j++) {
            if (adjacentMatrix[cur][j] != 0) {
                return hasCircle(u, j, false);
            }
        }
        return false;
    }
}
